package problem493;

//493.翻转对
//https://leetcode.cn/problems/reverse-pairs/description/

class Solution {
    public int reversePairs(int[] nums) {
        int ret =  mergeSort(nums, 0, nums.length-1);
        return ret;
    }
    public int mergeSort(int[] nums, int l, int r) {
        if(l >= r) return 0;
        int mid = l + (r-l)/2;
        //[l, mid] [mid+1, r]
        int ret = 0;
        ret += mergeSort(nums, l, mid);
        ret += mergeSort(nums, mid+1, r);

        int cur1 = l, cur2 = mid+1, i = 0;
        //统计
        while(cur1 <= mid && cur2 <= r) {
            if(nums[cur1]/2.0 > nums[cur2]) {
                ret += r-cur2+1;
                cur1++;
            }else {
                cur2++;
            }
        }

        cur1 = l; cur2 = mid+1; i = 0;
        int[] tmp = new int[r-l+1];
        while(cur1 <= mid && cur2 <= r) {
            if(nums[cur1] > nums[cur2]) {
                tmp[i++] = nums[cur1++];
            }else {
                tmp[i++] = nums[cur2++];
            }
        }
        while(cur1 <= mid) {
            tmp[i++] = nums[cur1++];
        }
        while(cur2 <= r) {
            tmp[i++] = nums[cur2++];
        }
        for(int j = l; j<=r; j++) {
            nums[j] = tmp[j-l];
        }

        return ret;
    }
}